import java.util.ArrayDeque;
import java.util.Deque;

/*
 * @lc app=leetcode.cn id=496 lang=java
 *
 * [496] 下一个更大元素 I
 */

// @lc code=start
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int n = nums1.length, m = nums2.length;
        int[] ans = new int[n];
        //1. 模拟 simulate
        for(int i = 0; i < n; i++){
            int j = 0;
            //先找到nums1[i]在nums2中对应的位置  find nums1[i]'s position in nums2.
            while(j < m && nums1[i] != nums2[j]){
                ++j;
            }
            //然后找接下来一个比它大的数  then find a number bigger nums1[i].
            while(j < m && nums1[i] >= nums2[j]){
                ++j;
            }
            //if j == m and don't find legal ans[i], return -1.
            ans[i] = j < m ? nums2[j] : -1;
        }
        //2. 单调栈
        
        // //target: find first one bigger in nums2[] than the number in nums[1].
        // //维护一个单调栈
        // Deque<Integer> d = new ArrayDeque<>();

        return ans;
    }
}
// @lc code=end

